265D - Good Sequences - CodeForces Solution

///Kan FI SORA LEKE BLWARD
#include<bits/stdc++.h>

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

#define all(v) v.begin() , v.end()
#define Pi 3.14159
#define sz(x) int(x.size())
#define OO 1e17

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

int MOD = 1e9 + 7 ;

ll gcd(ll a, ll b) { return ((b == 0) ? a : gcd(b, a % b)); }
ll lcm(ll a, ll b) { return (b / gcd(a, b)) * a; }

void Omani () {
ios::sync_with_stdio(0); cin.tie(0), cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
#endif
#ifdef _LOCAL_DEFINE
  cerr << (double)clock() * 1.0 / CLOCKS_PER_SEC << endl;
#endif
}


typedef tree<string, null_type,less_equal<string>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order (num of elemnts smaller than X) , order_of_key(elemnt in K-th indx)


#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(ll t) {cerr << t;}
void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(lld t) {cerr << t;}
void _print(double t) {cerr << t;}
void _print(ull t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.first); cerr << ","; _print(p.second); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

const int N = 1e5 + 10;
int dp_div[N] ;

void Solve() {

    int n ;
    cin >> n ;

    int ans = 1;

    for (int i = 1 ; i <= n ; i++) {

        int x ;
        cin >> x ;

        vector < int > PrimesFactors ;

        for (int div = 2 ; div * div <= x ; div++) {

            if (x % div == 0) {

                PrimesFactors.push_back(div) ;

                while (x % div == 0)
                    x /= div ;

            }

        }

        if (x > 1)
            PrimesFactors.push_back(x) ;

        int mx = 0 ;

        for (auto &it : PrimesFactors)
            mx = max(mx , dp_div[it]) ;

        ans = max(ans , mx + 1) ;

        for (auto&it : PrimesFactors)
            dp_div[it] = mx + 1 ;

    }

    cout << ans << endl;

}

int main() {
Omani() ;
int T = 1 ;                                         ///cin >> T ;
while(T--) Solve() ;
}